1. Field of the Invention
The present invention generally relates to a process scheduler for a computer system (hereunder sometimes referred to as a computer-system process scheduler), which uses a process scheduler supported by an operating system so as to cause a user-level process scheduler to function. More particularly, the present invention relates to a computer-system process scheduler that uses a process scheduler, which establishes fixed priorities respectively corresponding to a plurality of processes to be scheduled (namely, objects of scheduling) and next allocates a central processing unit (CPU) to a plurality of executable processes in the descending order of the priorities thereof and further causes the CPU to operate, so as to allow a user-level process scheduler to function.
2. Description of the Related Art
Generally, a plurality of programs are executed concurrently in a computer, so that a plurality of executable units (namely, run units) named as xe2x80x9cprocessesxe2x80x9d are permitted to be present therein. At that time, it is necessary to assign the CPU to each process according to an algorithm. Such assignment of the CPU to a process is referred to as xe2x80x9cprocess schedulingxe2x80x9d. Conventional process scheduling is-performed in a batch system or by a time-sharing system. Further, conventional process schedulers were created for the purpose of increasing the CPU utilization (efficiency) of the entire system. In the case of time-sharing systems, reduction in response time required to respond to a user""s operation (namely, the improvement of response performance) was further taken into account. It, however, has been regarded as being inevitable that the response time becomes long under heavy load conditions of the systems. Thus, there is no guarantee on the utilization of the CPU by user processes. Additionally, in the case of controlling built-in equipment which requires real time processing, all processes to be executed can be known when designed. Consequently, a fixed-priority scheduler, by which fixed priorities are assigned to the processes and a process of a priority higher than the priorities of other processes is preferentially executed, is used.
Meanwhile, with the recent development of multi-media systems, process schedulers for computers have come to handle videos and audios. In order to reproduce videos and audios smoothly, certain processes should be carried out securely at predetermined time intervals. In the case of such a conventional multi-media system, the conventional scheduling has the following problems:
I. In the case of the scheduling performed in the conventional batch system or in the conventional time-sharing system, there is no guarantee concerning when and how a CPU can-be utilized therein. In the case of employing such scheduling, the CPU cannot be utilized when a multi-media application program becomes necessary. As a result, when reproducing video data, a moving object generated in reproduced images does not appear to move smoothly.
II. The multi-media application programs are different from programs for controlling the built-in equipment in that the multi-media application programs cannot predict what processes or programs will be executed. The multi-media application programs, therefore, cannot preliminarily establish the priorities of processes (namely, assign the priorities to the processes, respectively). The conventional scheduling, which uses fixed priorities, cannot achieve the purpose of the schedulers. This problem also arises in the case of employing a rate monotonic scheduling method by which, among periodic processes, a process having a period shorter than those of the other processes is preferentially executed.
III. The multi-media application programs are further different from programs for controlling the built-in equipment in that the reliability of a run of the multi-media application is low. For example, if a certain multi-media application program permanentally uses a CPU on purpose or by mistake, programs having priorities lower than that of the process occupying the CPU do not run at all in the case that the scheduling is performed by using the fixed priorities. An occurrence of such a situation is not allowed in a general-purpose multi-media system.
For the aforementioned reasons, there has now emerged a need for a new process scheduling method which is available in a multi-media system. The research and development of such a process scheduling method are currently pursued. Incidentally, there are two cases or manners of introducing a new process scheduler, which is suitable for a multi-media system, thereinto. Namely, in a first case, the process scheduling is performed in an operating system. Further, in a second case, the process scheduling is carried out by a user program which runs or operates on (namely, under the control of) an operating system. Hitherto, the following problems, however, have arisen in the case when such a process scheduler is introduced into a multi-media system.
(1) Problems caused when introducing such a new process scheduler into the operating system:
(i) Conventional operating systems do not permit any persons other than developers thereof to add a process scheduler thereto or modify the process scheduler thereof. A source code of the operating system and a development environment, in which the operating system is developed, are necessary for changing the scheduler thereof. In the case of commercial operating systems, generally, persons other than developers thereof cannot get the source codes thereof. Even if a person other than the developers could get the source code of a commercial operating system, he should pay a very expensive royalty fee. Actually, it is impossible for a developer of a multi-media system to modify the process scheduler of the commercial operating system.
(ii) In the case of non-commercial operating systems, persons other than developers thereof may be able to get the source codes of some of the non-commercial operating systems free of charge. However, if the source code of such a non-commercial operating system is obtained, this non-commercial operating system cannot allow a large number of application programs to run. Moreover, there is a problem in a system to support users or the persons who have got the source codes. The present conditions, therefore, do not permit non-experts of an operating system for a computer to utilize non-commercial operating systems.
(iii) Whether an operating system to be modified is a commercial one or a non-commercial one, general knowledge concerning an operating system and comprehension of an operating-system installing method peculiar to the operating system are required to modify the operating system.
(2) Problems caused when introducing the new process scheduler into the operating system by executing a user program:
(i) There has been a method for realizing a pseudo process (namely, a user-level thread) in a user own process by a user program or a library utilized by a user program and for scheduling of user-level threads. This method, however, can perform the scheduling only in the process. Therefore, in the case that there are other groups of processes which utilize a CPU required by a multi-media system, the utilization of the CPU required by the multi-media system cannot be ensured.
(ii) Further, there has been a method by which a user program becomes a scheduler and this scheduler gives a user process a priority used by a fixed-priority scheduler which is supported by an operating system. Namely, this method utilizes the scheduling (function) provided by the operating system. Consequently, the utilization of the CPU in the user process needed by the multi-media system cannot be ensured.
(iii) Generally, the modification of the user program becomes further necessary in the aforementioned cases of (2)(i) and (2)(ii).
As is understood from the foregoing description, in the case of the conventional process schedulers, it is very difficult to introduce a new (conventional) process scheduler, which is required by a multi-media system, thereinto.
The present invention is accomplished to solve the aforementioned problems of the conventional process schedulers.
In accordance with the present invention, there is provided a computer(-system) process scheduler which can ensure the utilization of a CPU in a user process required by a multi-media system while the scheduling is carried out by means of a user program by utilizing a scheduler supported by an operating system.
The computer-system process scheduler (hereunder sometimes referred to simply as a computer process scheduler) of the present invention is based on the premise that this computer process scheduler is the following fixed-priority process scheduler. Namely, the computer process scheduler is supported by an operating system (OS) and establishes fixed priorities respectively corresponding to processes to be scheduled. Further, the priorities can be changed by designation sent from a user process and that the computer process scheduler allocates a CPU to executable ones of the processes in the descending order of the priorities thereof and causes the process, to which the CPU is allocated, to operate or run. The computer process scheduler of the present invention is characterized in that a user-level process scheduler is provided in such a fixed-priority process scheduler, namely, in a real-time-class process scheduler. The user-level process scheduler has a real-time-class first priority of 159 and is operative to schedule other processes, each of which has a priority lower than the first priority of 159 and to cause the latter processes to operate or run. Namely, the user-level process scheduler determines the allocation of the CPU thereto and requests the operating system to execute the user process.
A practical embodiment of the computer process scheduler of the present invention may be a distributed (type) computer process scheduler, by which a user-level process scheduler is linked to each of a plurality of user processes having the first priority of 159 and is operative to schedule the user process corresponding thereto and cause the corresponding user process to operate or run.
Further, another practical embodiment of the computer process scheduler of the present invention may be a hierarchical (or layer type) computer process scheduler, by which the user-level process scheduler having the first priority of 159 provides or establishes a user-level process scheduler of a second priority in a group of user processes scheduled by the scheduler having the first priority and is operative to hierarchically schedule other groups of user processes from those of high-order groups to those of low-order groups and cause these groups of the user processes to operate or run. Incidentally, this hierarchical technique or method may be applied to the aforementioned distributed type scheduler. Namely, this practical embodiment of the present invention may be of the hierarchically distributed type.
Moreover, in the case of still anther practical embodiment of the present invention, there are provided a plurality of user-level process schedulers having the first priority, each of which individually schedules a corresponding group of user processes and causes the corresponding group of user processes to operate or run.
Each of the user-level process scheduler has a process execution control portion that is operative to request the operating system to execute, halt (or suspend) or resume a user process designated according to an instruction, which is based on a request or demand from a user process and is sent from a class change instructing portion, or another instruction which is issued from a process execution instructing portion by referring to a process management table. Moreover, each of the user-level process scheduler has a process priority control portion that is operative to request the operating system to execute, halt (or suspend) or resume a user process designated according to an instruction, which is based on a request or demand from a user process and is sent from a class change instructing portion, or another instruction, which is issued from a process execution instructing portion by referring to a process management table, in such a manner as to execute a designated user process A by changing the priority of the user process A into the first priority and in such a way as to halt (or suspend) another designated user process B by changing the priority of the user process B into a lower priority. Furthermore, each of the user process schedulers has a class change control portion that is operative to request the operating system to change a designated class and to execute, halt (or suspend) or resume the execution of a user process designated according to an instruction, which is based on a request or demand from a user process and is sent from the class change instructing portion, or another instruction, which is issued from the process execution instructing portion by referring to the process management table, in the case that the operating system has a scheduling class, for example, a time sharing class, which is dynamically changed according to the state of a process in the range of low priorities (namely, of 0 to 50) differently from a fixed-priority real time class established in the range of high priorities (namely, of 100 to 159).
Hereat, in response to a demand (or request) for admission, which is issued by a new user process and is accompanied by designation of CPU (utilization) time demanded by the new user process, the class change instructing portion obtains a total of CPU time demanded by one or more user processes, each of which is currently in an admitted state, by referring the process management table. Further, if the total CPU time is equal to or less than a prescribed time of period, the class change instructing portion permits the admission of the new user process. In contrast, if the total CPU time exceeds the prescribed time, the class change instructing portion rejects the admission thereof. Moreover, an admission processing is as follows. Namely, in the case that the class change instructing portion permits the admission of a new user process, the class change instructing portion instructs the process execution control portion to change the state of an admission demanding process (namely, a user process having demanded the admission thereof) into an halted (or suspended) state. Moreover, the class change instructing portion instructs the class change control portion to change the current scheduling class of the admission demanding process into a real time class. Furthermore, the class change instructing portion instructs the process priority control portion to change the priority of the admission demanding process into the second priority. In addition, after the admission demanding process is registered in the process management table, the class change instructing portion posts the permission for the admission to the admission demanding process (namely, notifies the admission demanding process of the permission for admission).
Moreover, another manner of performing the admission processing is as follows. Namely, in the case that the class change instructing portion permits the admission of a new user process, the class change instructing portion instructs the class change control portion to change the current scheduling class of the admission demanding process from the time-sharing class into the real time class. Moreover, the class change instructing portion instructs the process priority control portion to change the priority of the admission demanding process into, for instance, the lowest priority (namely, 100) of the real time class. Furthermore, after the admission demanding process is registered in the process management table, the class change instructing portion posts the permission for the admission to the admission demanding process. Further, still another manner of performing the admission processing is as follows. Namely, in the case that the class change instructing portion permits the admission of a new user process, the class change instructing portion instructs the class change control portion to change the current scheduling class of the admission demanding process into the time sharing class. Moreover, after the admission demanding process is registered in the process management table, the class change instructing portion posts the permission for admission to the admission demanding process.
When a demand (or request) for exit (or withdrawal) is made by a user process, the class change instructing portion deletes this user process from the process management table and further instructs the class change control portion to change the current scheduling class of the user process, which has made the demand for an exit, into the time sharing class. The class change instructing portion can handle the admission and exit of a new user process in response to a notice sent from the user process. Moreover, the class change instructing portion can handle the admission and exit of a new user process in response to a notice sent from the operating system.
Furthermore, in the case of the computer(-system) process scheduler of the present invention, information concerning change requests, which are issued from the user-level process scheduler to the process execution control portion, the class change control portion and the process priority control portion, can be stored in the library. Moreover, in response to a request or instruction from an application program, a corresponding change is requested to the operating system by causing the library to post a message, which represents a request for a corresponding change, to a user-level process scheduler. Furthermore, the specifications of scheduling demands (or requests) for change to be made to the process execution control portion (hereunder sometimes referred to as the scheduling specifications), the class change control portion and the process priority control portion are generated by one of the user processes. A demand for change is posted to the user-level process scheduler on the basis of the scheduling specifications of the user process, and thus the process-scheduler requests the operating system to make the change. Hereupon, a user process to be scheduled by the user-level process scheduler consists of a plurality of threads. Further, the threads are scheduled by a thread scheduler that is a part of the user process.
When allocating the CPU time to one or more user processes registered in the process management table, the user-level process scheduler requests the operating system to execute and suspend (or stop the execution of) the user process and change the priority and the (scheduling) class thereof in such a manner that there is only one user process to which the CPU (time) can be allocated. Further, when allocating the CPU time to one or more user processes registered in the process management table, the user-level process scheduler requests the operating system to execute and suspend the user processes and change the priorities and the (scheduling) classes thereof in such a way that there are a plurality of user processes to which the CPU is allocated in a time sharing manner within a same period of the CPU time. Moreover, the user-level process scheduler ensure the operation or execution of a plurality of user processes within a certain period of time by allocating the CPU time to elements, which include the plurality of user processes and the user-level process scheduler itself, serially within the certain period of time. The user-level process scheduler further ensures the operation or execution of a plurality of user processes by establishing or setting certain periods and repeatedly allotting the CPU time to the elements, which include the plurality of user processes and the user-level process scheduler itself, serially within each of the certain periods. In the case that a plurality of user processes have different operating periods, respectively, the user-level process scheduler determines a combination of the different operating periods as a period, and allots available CPU time to the plurality of user processes serially within this period. Thereby, the user-level process scheduler ensures the execution or operation of each of the plurality of user processes. Furthermore, when the ratio of the CPU time, which is allocated to the plurality of user processes, to a certain time or period is equal to or less than a prescribed or predetermined value, the user-level process scheduler allows the allocation of CPU time to other user processes. Conversely, when such a ratio exceeds the prescribed value, the user-level process scheduler performs an admission control operation of rejecting the allocation of the CPU time to other user processes. In the case that CPU time is allocated to a user process in a certain time or at certain periods (or intervals), the user-level process scheduler may allocate continuous CPU time thereto. Alternatively, the user-level process scheduler may divide the CPU time, which is allocated to a group of a plurality of user processes, into time slices and also may allot time slices to the plurality of user processes, respectively.
In the case that the user processes registered in the process management table include user processes belonging to the fixed-priority real time class, whose priorities are in the range of high priorities (namely, 100 to 159), and further include other user processes belonging to the time sharing class, whose priorities are dynamically changed in the range of low priorities (namely, 0 to 50), the user-level process scheduler restricts the allocation of the CPU time to the user processes belonging to the real time class and allocates the CPU time to the user processes belonging to the time sharing class. The user-level process scheduler detects a halt (or suspension) of the execution of a user process and enables the execution of another user process. When allocating the CPU time to a user process, the user-level process scheduler provides a blocking detection process, which can be executed at the same priority as of the user process, in addition to th user process. Then, when the user process is blocked due to input-output (I/O) waiting or the like, the user-level process scheduler allocates CPU time to a blocking detection process so that the blocking detection process detects an occurrence of blocking and then posts the occurrence of blocking to the user-level process scheduler. Thereby, the user-level process scheduler recognizes that the execution of the user process is halted or stopped. Then, the user-level process scheduler enables another user process to be executed. Moreover, when allocating CPU time to a user process, the user-level process scheduler further provides or establishes a blocking detection process which can be executed at a priority lower than that of the user process. Furthermore, when the user process is blocked owing to I/O waiting or the like, the user-level process scheduler allocates CPU time to this blocking detection process so that the blocking detection process detects an occurrence of blocking and then posts the occurrence of blocking to the user-level process scheduler. Thereby, the user-level process scheduler recognizes that the execution of the user process is halted or stopped. Then, the user-level process scheduler enables another user process to be executed. Additionally, the user-level process scheduler is operative to detect a change of the state of the blocked user process into a ready or executable state, namely, a state in which this user process can be executed. Then, the user-level process scheduler causes this user process to run or operate. In addition, the user-level process scheduler can detect a notice indicating the blocking of a user process by the operating system or indicating the resumption of the blocked user process by recovering the blocked user process. Then, the user-level process scheduler can execute or suspend another user process.
Such a user-level process scheduler of the present invention can obtain the following advantages:
I. There can be realized a scheduler which allocates certain CPU time to a process to be scheduled (namely, an object of the scheduling) and thus ensures the utilization of the CPU by the process.
II. A user process can be scheduled (namely, an object of the scheduling) without modifying a program which has previously been executed. There is no necessity of modifying the program for a new scheduler and of linking the program thereto anew.
III. Source code of an operating system is not necessary for realizing a new scheduler.
IV. The scheduler of the present invention can be utilized under the control of the commercial operating system.
V. Knowledge concerning the inner structure of the operating system is unnecessary for realizing the new scheduler.
VI. When trying various kinds of schedulers, it is unnecessary to restart the system.
VII. There can be realized a scheduler, by which even if a program behaving unreliably is an object of the scheduling, the execution of another program can be performed.
As a result, in accordance with the present invention, various schedulers, such as a scheduler to ensure certain CPU utilization needed for multi-media processing, can be implemented on a commercial operating system. Further, a program behaving unreliably can be employed as an object of the scheduling. Namely, a scheduler, which is equivalent to a scheduler implemented in the operating system, can be implemented as a user-level process scheduler.
Other features, objects and advantages of the present invention will become apparent from the following description of a preferred embodiment with reference to the drawings in which like reference characters designate like or corresponding parts throughout several views.